package com.dycong.common.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author dycong
 * @date 2019/8/6 8:51
 */
public class MaxSlidingWindow_239 {

    public static void main(String[] args) {
        int[] nums = {9, 8, 8, 6, 7, 3, 2, 6};
        int k = 3;
        for (int i : maxSlidingWindow2(nums, k)) {
            System.out.print(i + ",");
        }
    }

    /**
     * 借助一个辅助队列（双端队列），从头遍历数组，根据如下规则进行入队列或出队列操作：
     * 1. 如果队列为空，则当前数字入队列
     * 2. 如果当前数字大于队列尾，则删除队列尾，直到当前数字小于等于队列尾，或者队列空，然后当前数字入队列
     * 3. 如果队列头超出滑动窗口范围，则删除队列头
     * 这样能始终保证队列头为当前的最大值
     *
     * @param nums
     * @param k
     * @return
     */

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k <= 0 || k > nums.length) {
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        // window 存储下标
        Deque<Integer> window = new ArrayDeque<>(k);
        for (int i = 0; i < nums.length; i++) {
            //如果队列头超出滑动窗口范围，则删除队列头
            if (i >= k && window.peekFirst() <= i - k) {
                window.pollFirst();
            }

            //如果当前数字大于队列尾，则删除队列尾，直到当前数字小于等于队列尾，或者队列空，然后当前数字入队列
            while (!window.isEmpty() && nums[window.peekLast()] <= nums[i]) {
                window.pollLast();
            }
            window.addLast(i);
            if (i >= k - 1) {
                //这样能始终保证队列头为当前的最大值
                res[i - k + 1] = nums[window.peekFirst()];
            }
        }
        return res;
    }

    /**
     * 针对 {9, 8, 8, 6, 7, 3, 2, 6} 这种 一个时刻，最大值在窗口中部的有问题
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0 || k <= 0) {
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        // window 存储下标
        Deque<Integer> window = new ArrayDeque<>(k);
        for (int i = 0; i < nums.length; i++) {
            if (i >= k && window.peekFirst() <= i - k) {
                window.pollFirst();
            }

            //将双端队列中小于即将进入元素的所有元素剔除
            while (!window.isEmpty() && nums[window.peekFirst()] <= nums[i]) {
                window.pollFirst();
            }
            window.add(i);
            if (i >= k - 1) {
                res[i - k + 1] = nums[window.peekFirst()];
            }
        }
        return res;
    }
}
